package com.fanshuai.heap;

/**
 * 极大堆
 * 堆为完全二叉树，特点为：
 * 父节点的值大于等于子节点的值。
 * 父节点的值大于等于左右子树的值
 *
 * 使用数组实现堆
 * 索引从1开始时，对于节点i，子节点为2i, 2i+1; 父节点为i/2
 * 索引从0开始时，对于节点i, 子节点为2i+1, 2i+2；父节点为(i-1)/2
 * @param <E>
 */
public class MaxHeap<E extends Comparable<E>> implements Heap<E> {
    private E[] array;
    private int index;

    public MaxHeap(int maxSize) {
        array = (E[]) new Object[maxSize + 1];
        index = 1;
    }

    private void swap(int i, int j) {
        E data = array[i];
        array[i] = array[j];
        array[j] = data;
        data = null;
    }

    /**
     * 冒泡操作。新加入元素位于堆的末尾，冒泡操作保证堆有序
     */
    private void swim() {
        int curIndex = index - 1;

        while (curIndex > 1) {
            if (array[curIndex].compareTo(array[curIndex / 2]) > 0) {
                swap(curIndex, curIndex / 2);
                curIndex = curIndex / 2;
            } else {
                break;
            }
        }
    }

    /**
     * 沉底操作。弹出根节点后，末尾节点加入根节点，同时做沉底操作，保证堆有序
     */
    private void sink() {
        int curIndex = 1;
        while (2 * curIndex <= index - 1) {
            int j = curIndex * 2;
            if (j < index - 1 && array[j + 1].compareTo(array[j]) > 0) {
                j = j + 1;
            }

            if (array[j].compareTo(array[curIndex]) > 0) {
                swap(curIndex, j);
                curIndex = j;
            } else {
                break;
            }
        }
    }

    @Override
    public void add(E data) throws IndexOutOfBoundsException {
        if (index >= array.length) {
            throw new IndexOutOfBoundsException("out of bounds, index=" + index);
        }

        array[index] = data;
        index++;
        //冒泡操作
        swim();
    }

    @Override
    public E pop() {
        if (index <= 1) {
            return null;
        }

        //弹出根节点，将最后一个节点赋值根节点
        E data = array[1];
        array[1] = array[index - 1];
        array[index - 1] = null;
        index--;

        //沉底操作
        sink();

        return data;
    }

    @Override
    public E peek() {
        return array[1];
    }

    @Override
    public int size() {
        return index - 1;
    }

    @Override
    public boolean isEmpty() {
        return index == 1;
    }

    @Override
    public boolean isFull() {
        return index == array.length;
    }
}
